#include <iostream>
#include <vector>
#include <string.h>
using std::cout;
using std::endl;
using std::vector;

template <typename T,typename Compare = std::less<T>>
class MyQsort
{
public:
    MyQsort(T *arr, size_t size, Compare com);//if(a < b)  if(com(a, b))
    void quick(int left, int right, Compare &);
    int partition(int left, int right, Compare &);
    void print();
private:
    vector<T> _vec;
};

    template<typename T,typename Compare> 
MyQsort<T,Compare>::MyQsort(T *arr, size_t size, Compare com)
{
    for(size_t idx = 0;idx < size; ++idx){
        _vec.push_back(arr[idx]);
    }
    quick(0,_vec.size() - 1,com);
}

template<typename T,typename Compare> 
void MyQsort<T,Compare>::quick(int left, int right, Compare &com){
    if(left >= right)
        return;
    int idx = partition(left,right,com);
    quick(left,idx - 1,com);
    quick(idx + 1,right,com);
}

template<typename T,typename Compare> 
int MyQsort<T,Compare>::partition(int left, int right, Compare &com){
    T pivot = _vec[left];
    int i = left,j = right;
    while(i < j){
        while(i < j && com(pivot,_vec[j])){
            j--;
        }
        _vec[i] = _vec[j];
        while(i < j && com(_vec[i],pivot)){
            i++;
        }
        _vec[j] = _vec[i];
    }
    _vec[i] = pivot;
    return i;
}     

template<typename T,typename Compare> 
void MyQsort<T,Compare>::print(){
    for(auto & elem : _vec){
        cout << elem << " ";
    }
    cout << endl;
} 



void test0(){
    int arr[] = {6,4,90,2,1,53,27};
    std::less<int> com;
    MyQsort<int> mq(arr,7,com);
    mq.print(); 
}

int main(int argc, char * argv[])
{
    test0();
    return 0;
}


